package main.leetcode.primary.from801to900;

/**
 * 877. 石子游戏
 *
 * <p>亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
 *
 * <p>游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
 *
 * <p>亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
 *
 * <p>假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
 *
 * <p>示例：<br>
 * 输入：[5,3,4,5] <br>
 * 输出：true <br>
 * 解释： 亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得
 * 10 分。 如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。 这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。
 *
 * <p>提示：<br>
 * 2 <= piles.length <= 500 <br>
 * piles.length 是偶数。 <br>
 * 1 <= piles[i] <= 500 <br>
 * sum(piles) 是奇数。
 */
public class ex877 {
    public static void main(String[] args) {
        System.out.println(new ex877().stoneGame(new int[] {5, 3, 4, 5}));
    }

    /** 数学解法 —— 博弈论 */
    public boolean stoneGame(int[] piles) {
        // ①堆数为偶数 => 下标为奇数的石子堆数A == 下标为偶数的石子堆数B
        // ②石子总和为奇数 => A中所有石子的总和 != B中所有石子的总和
        // ③先手 => 每一轮拿到的石子堆的下标都和第一轮下标的奇偶性一致
        // 所以先手玩家只要计算下标为奇数的所有石子堆中石子的总和和下表为偶数的总和，就可以“先下手为强”了
        return true;
    }

    //    /** 动态规划 —— 状态压缩 */
    //    public boolean stoneGame(int[] piles) {
    //        int n = piles.length;
    //        int[] dp = new int[n];
    //        for (int i = n - 2; i >= 0; --i) {
    //            for (int j = i + 1; j < n; ++j) {
    //                dp[j] = Math.max(piles[i] - dp[j], piles[j] - dp[j - 1]);
    //            }
    //        }
    //        return dp[n - 1] >= 0;
    //    }

    //    /** 动态规划 */
    //    public boolean stoneGame(int[] piles) {
    //        int n = piles.length;
    //        int[][] dp = new int[n][n];
    //        // 此题无需初始化 dp[i][i] = piles[i]
    //        for (int i = n - 2; i >= 0; --i) {
    //            for (int j = i + 1; j < n; ++j) {
    //                dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
    //            }
    //        }
    //        return dp[0][n - 1] >= 0;
    //    }

    //    /** 记忆化搜索 */
    //    public boolean stoneGame(int[] piles) {
    //        int n = piles.length;
    //
    //        int[][] memo = new int[n][n];
    //        for (int[] ints : memo) {
    //            // 使用「相对分数可能存在负数，所以不能以0为初始值
    //            Arrays.fill(ints, Integer.MIN_VALUE);
    //        }
    //        return memorize(0, n - 1, piles, memo) >= 0;
    //    }
    //
    //    private int memorize(int i, int j, int[] piles, int[][] memo) {
    //        if (i == j) {
    //            return piles[i];
    //        }
    //        if (memo[i][j] != Integer.MIN_VALUE) {
    //            return memo[i][j];
    //        }
    //        int left = piles[i] - memorize(i + 1, j, piles, memo);
    //        int right = piles[j] - memorize(i, j - 1, piles, memo);
    //        return memo[i][j] = Math.max(left, right);
    //    }

    //    /** 递归 */
    //    public boolean stoneGame(int[] piles) {
    //        return dfs(0, 0, piles, 0, 0, true);
    //    }
    //
    //    private boolean dfs(int l, int r, int[] nums, int sum1, int sum2, boolean flag) {
    //        if (l > r) {
    //            return sum1 > sum2;
    //        }
    //        if (flag) {
    //            // 如果本轮是亚历克斯先手，则只要任意一次获胜即可
    //            return dfs(l + 1, r, nums, sum1 + nums[l], sum2, false)
    //                    || dfs(l, r - 1, nums, sum1 + nums[r], sum2, false);
    //        }
    //        // 如果本轮是李先手，则需要
    //        return dfs(l + 1, r, nums, sum1, sum2 + nums[l], true)
    //                && dfs(l, r - 1, nums, sum1, sum2 + nums[r], true);
    //    }
}
